from ast import List
import collections


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        q = collections.deque([root])
        level = 0
        while q:
            size = len(q)
            path = []
            for i in range(size):
                node = q.popleft()
                if level %2==1:
                    path.insert(0, node.val)
                else:
                    path.append(node.val)
                if node.left:q.append(node.left)
                if node.right:q.append(node.right)
            res.append(path)
            level += 1
        return res


